#-*- coding: utf-8 -*-



import sys

def mergeSort(A, p, r):
    ''' 
    Parametros de entrada 
        A -> Array para odernacao 
        p -> Possicao de inicio
        r -> Tamanho do array
    '''
    if p < r:
        q = (p+r)/2
        mergeSort(A,p,q)
        mergeSort(A,q+1,r)
        merge(A,p,q,r)
        pass
    pass
pass

def merge(A,p,q,r):
    ''' 
    Algoritmo de ordenacao Merge
    Parametros de entrada 
        A -> Array para odernacao 
        p -> Possicao de inicio
        q -> meio do array
        r -> Tamanho do array
    '''
    n1 = q - p + 1
    n2 = r - q
    L = [0 for k in range(n1+1)]
    R = [0 for k in range(n2+1)]

    for k in range(n1):
        L[k] = A[p + k]
    pass
    for k in range(n2):
        R[k] = A[q + k + 1]
    pass

    L[n1] = R[n2] = sys.maxint
    i = j = 0

    for k in range(p, r + 1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
        pass
    pass
pass


